// 版权归Go作者所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 页分配器。
// 
// 页面分配器管理映射页面（由pageSize定义，而不是
// physPageSize）以进行分配和重用。它嵌入到mheap中。
// 
// 使用分块的位图管理页面。
// 位图中，1表示正在使用，0表示免费。位图跨越
// 进程的地址空间。块在稀疏数组样式的结构
// 中进行管理，类似于mheap.arenas，因为位图在某些系统上可能较大。
// 
// 该位图通过使用基数树结合
// 和快速位内部函数进行有效搜索。使用地址顺序
// 第一次拟合方法执行分配。
// 
// 基数树中的每个条目都是一个摘要，描述了
// 地址空间的一个特定区域的三个属性：在它所代表的区域的开始和结束处的连续空闲页数
// ，以及在该地区任何地方发现的最大
// 连续免费页面数。
// 
// 基树的每一级存储为一个连续数组，表示进程地址空间的不同细分粒度。因此，这个
// 基树实际上隐含在这些大型数组中，而不是具有显式的
// 动态分配的基于指针的节点结构。当然，对于具有大地址空间的系统来说，这些数组可能非常大，因此在这些情况下，它们会根据需要映射到内存中。树的叶摘要对应于位图块。
// 
// 根级别（在pageAlloc.summary中称为L0和索引0）具有每个
// summary表示地址空间的最大部分（64位系统上为16 GiB），
// 每个后续级别代表连续较小的子部分，直到我们
// 在叶子处达到最细的粒度，即块。
// 
// 更具体地说，每个级别的每个摘要（叶子摘要除外）
// 表示以下级别的一些条目数。例如，根级别中的每个
// 摘要可能代表地址空间的16 GiB区域，
// 在下一级别中可能有8个对应的条目，它们代表该16 GiB区域的2个
// GiB子段，每个可对应于下一级中的8个
// 条目，每个条目代表256个MiB区域，依此类推。
// 
// 因此，此设计只能扩展到如此大的堆，但始终可以通过简单地向基树添加级别来扩展到更大的堆，这主要需要额外的虚拟地址空间。选择管理大型阵列还意味着
// 运行时可能会保留大量虚拟地址空间。AbDefg

package runtime

import (
	"runtime/internal/atomic"
	"unsafe"
)

const (
	pallocChunkPages    = 1 << logPallocChunkPages
	pallocChunkBytes    = pallocChunkPages * pageSize
	logPallocChunkPages = 9
	logPallocChunkBytes = logPallocChunkPages + pageShift

	// 每个级别的基数位数。
	// 
	// 选择值3时，我们需要在
	// 每个级别扫描的摘要块适合64个字节（每个摘要2^3个摘要*8个字节），这是
	// 在许多系统上接近一级缓存的线宽。此外，值3将4个树
	// 级别完美地匹配到根级别的21位pallocBits摘要字段中。
	// 
	// 下面的等式解释了每个常量之间的关系：
	// Summary10bits+（summaryLevels-1）*summaryLevelBits+logPallocChunkBytes=HeapArbits 
	// 
	// summaryLevels是在mpagealloc_*.go中定义的依赖于体系结构的值。
	summaryLevelBits = 3
	summaryL0Bits    = heapAddrBits - logPallocChunkBytes - (summaryLevels-1)*summaryLevelBits

	// pallocChunksL2Bits是块索引号
	// 由块映射的第二级覆盖的位数。
	// 
	// 有关详细信息，请参阅（*pageAlloc）.chunks。更新文件
	// 应该有此更改。
	pallocChunksL2Bits  = heapAddrBits - logPallocChunkBytes - pallocChunksL1Bits
	pallocChunksL1Shift = pallocChunksL2Bits
)

// searchAddr的最大值，表示堆没有可用空间。
// 
// 我们别名maxOffAddr只是为了明确这是页面分配器搜索空间的最大地址
// 。有关详细信息，请参阅maxOffAddr。
var maxSearchAddr = maxOffAddr

// 全局块索引。
// 
// 表示根树的叶级索引。
// 类似于arenaIndex，除了代替arenas之外，它将地址
// 空间划分为块。
type chunkIdx uint

// chunkIndex返回包含
// 指针p的palloc块的全局索引。
func chunkIndex(p uintptr) chunkIdx {
	return chunkIdx((p - arenaBaseOffset) / pallocChunkBytes)
}

// chunkIndex返回索引ci处palloc块的基址。
func chunkBase(ci chunkIdx) uintptr {
	return uintptr(ci)*pallocChunkBytes + arenaBaseOffset
}

// chunkPageIndex计算包含p的页面的索引，
// 相对于包含p的区块。
func chunkPageIndex(p uintptr) uint {
	return uint(p % pallocChunkBytes / pageSize)
}

// l1将索引返回到（*pageAlloc）.chunks的第一级。
func (i chunkIdx) l1() uint {
	if pallocChunksL1Bits == 0 {
		// 如果没有
		// L1映射，让编译器优化它。
		return 0
	} else {
		return uint(i) >> pallocChunksL1Shift
	}
}

// l2将索引返回到（*pageAlloc）.chunks的第二级。
func (i chunkIdx) l2() uint {
	if pallocChunksL1Bits == 0 {
		return uint(i)
	} else {
		return uint(i) & (1<<pallocChunksL2Bits - 1)
	}
}

// offAddrToLevelIndex将偏移地址空间
// 中的地址转换为包含addr的摘要[level]。
func offAddrToLevelIndex(level int, addr offAddr) int {
	return int((addr.a - arenaBaseOffset) >> levelShift[level])
}

// levelIndexToOffAddress将索引转换为摘要[level]并转换为偏移地址空间中相应的地址。
func levelIndexToOffAddr(level, idx int) offAddr {
	return offAddr{(uintptr(idx) << levelShift[level]) + arenaBaseOffset}
}

// addrsToSummaryRange将基指针和限制指针转换为给定摘要级别的条目范围
// 。
// 
// 返回的范围在下限为包含，在上限为独占。
func addrsToSummaryRange(level int, base, limit uintptr) (lo int, hi int) {
	// 这比独家
	// 上限的变化稍微微妙一些。请注意，排他上界可能在这个级别的
	// 摘要中，这意味着如果我们只进行明显的计算，
	// hi将最终成为一个包含上界。不幸的是，仅仅是
	// 加上1太宽了，因为我们可能就在这个级别的摘要最大页数边界
	// 的边缘
	// （1<<levelLogPages[level]）。所以，将限制设为包含的上界
	// 然后移位，然后加1，这样我们在最后得到一个独占的上界。
	lo = int((base - arenaBaseOffset) >> levelShift[level])
	hi = int(((limit-1)-arenaBaseOffset)>>levelShift[level]) + 1
	return
}

// blockAlignSummaryRange将给定级别的索引与该
// 级别的块宽度（1<<levelBits[level]）对齐。它假定lo是包含的
// 而hi是独占的，因此将它们分别向下和向上对齐。
func blockAlignSummaryRange(level int, lo, hi int) (int, int) {
	e := uintptr(1) << levelBits[level]
	return int(alignDown(uintptr(lo), e)), int(alignUp(uintptr(hi), e))
}

type pageAlloc struct {
	// 摘要的基树。
	// 
	// 每个片的上限代表整个内存保留。
	// 每个片的len反映了分配器已知的最大
	// 该级别的映射堆地址。
	// 
	// 每个摘要级别的备份存储在init 
	// 中保留，可以在grow中提交，也可以不提交（小地址空间
	// 可以提交init中的所有内存）。
	// 
	// 保持len<=cap的目的是在切片的顶端强制执行边界检查
	// 这样，我们得到的是一个更友好的越界错误，而不是未知的
	// 运行时分段错误。
	// 
	// 若要在摘要级别上迭代，请使用inUse确定当前可用的范围
	// 。否则，可能会尝试访问
	// 仅保留的内存，这可能会导致硬故障。
	// 
	// 我们仍然可能会出现分段错误<len，因为其中一些
	// 内存可能尚未提交。
	summary [summaryLevels][]pallocSum

	// 块是位图块的一部分。
	// 
	// 在大多数64位平台上，数据块的总大小相当大
	// （O（GiB）或更多）如果被展平，那么就不要制作一个大映射
	// （在某些平台上有问题，即使没有保护）我们使用了一种类似于mheap中arena索引的
	// 两级稀疏数组方法。
	// 
	// 若要查找包含内存地址“a”的块，请执行以下操作：
	// chunkOf（chunkIndex（a））
	// 
	// 下面是一个表，描述运行时支持的各种
	// HeapArbits的块配置。
	// 
	// HEAPARBITS | L1位| L2位| L2项大小
	// ----------------------------------------
	// 32 | 0 | 10 | 128 KiB 
	// 33（iOS）|0 | 11 | 256 KiB 
	// 48 | 13 | 13 | 1 MiB 
	// 
	// 没有理由在32位上使用块的L1部分，
	// 地址空间很小，因此L2很小。对于带有
	// 48位地址空间，我们选择L1，使L2的大小为1 MiB 
	// ，这是低粒度与无
	// 对BSS的影响之间的良好平衡（注意L1直接存储在pageAlloc中
	// ）。
	// 
	// 要在位图上迭代，请使用inUse确定当前可用的范围
	// 。否则，您可能会迭代未使用的
	// 范围。ABCFDG 
	chunks [1 << pallocChunksL1Bits]*[1 << pallocChunksL2Bits]pallocData

	// 开始分配搜索的地址。它决不能指向inUse中未包含的任何内存，即，inUse.contains（searchAddr.addr（））必须始终为true。此规则的一个例外是，它可能采用
	// maxOffAddr的值来表示堆已耗尽。
	// 
	// 我们保证分配低于此值
	// 的所有有效堆地址，不值得搜索。
	searchAddr offAddr

	// 开始和结束表示块索引
	// 这是pageAlloc知道的。它假设[start，end]范围内的块是当前可以使用的。inUse是地址空间范围的一部分，地址空间是页分配器已知的当前正在使用的（通过
	start, end chunkIdx

	// 增长）.
	// 
	// 此字段目前在32位体系结构上未使用，但
	// 对跟踪无害。在这些情况下，我们更关心的是拥有一个
	// 连续堆，并采取其他措施
	// 以确保这一点，因此在几乎所有情况下，这应该只有一个CDEFG
	// 
	// 所有访问都受mheapLock保护。
	inUse addrRanges

	// scav存储清道夫状态。
	// 
	// 所有字段都受mheapLock保护。
	scav struct {
		// inUse是没有
		inUse addrRanges

		// gen是清道夫生成数。
		gen uint32

		// reservationBytes是每个清道夫迭代的保留大小
		// 以字节为单位的地址空间。
		reservationBytes uintptr

		// released是这一代释放的内存量。
		released uintptr

		// scavLWM是清道夫到达此
		// 清道夫生成的最低（偏移量）地址。
		scavLWM offAddr

		// freeHWM是最高（偏移量）释放给
		// 此清除生成的页面分配器的页面地址。
		freeHWM offAddr
	}

	// mheap_uu2;.lock。此级别的间接寻址使
	// 可以独立于运行时分配器测试pageAlloc。
	mheapLock *mutex

	// sysStat是新系统
	// 内存由pageAlloc为分配元数据提交。
	sysStat *sysMemStat

	// 此结构是否正在测试中使用。
	test bool
}

func (p *pageAlloc) init(mheapLock *mutex, sysStat *sysMemStat) {
	if levelLogPages[0] > logMaxPackedValue {
		// 我们无法表示1<<levelLogPages[0]pages，我们需要在根级别表示的最大页数
		// 在摘要中，这是一个大问题。Throw.
		print("runtime: root level max pages = ", 1<<levelLogPages[0], "\n")
		print("runtime: summary max pages = ", maxPackedValue, "\n")
		throw("root level max pages doesn't fit in summary")
	}
	p.sysStat = sysStat

	// Initialize p.inUse.
	p.inUse.init(sysStat)

	// 依赖于系统的初始化。
	p.sysInit()

	// 以searchAddr的状态开始，表明没有空闲的memory.
	p.searchAddr = maxSearchAddr

	// 设置mheapLock.
	p.mheapLock = mheapLock

	// 初始化清除跟踪状态。
	p.scav.scavLWM = maxSearchAddr
}

// tryChunkOf返回给定块的位图数据。
// 
// 如果块数据未映射，则返回零。
func (p *pageAlloc) tryChunkOf(ci chunkIdx) *pallocData {
	l2 := p.chunks[ci.l1()]
	if l2 == nil {
		return nil
	}
	return &l2[ci.l2()]
}

// chunkOf返回给定块索引处的块。
// 
// 区块索引必须有效，否则此方法可能会抛出。
func (p *pageAlloc) chunkOf(ci chunkIdx) *pallocData {
	return &p.chunks[ci.l1()][ci.l2()]
}

// grow为地址范围设置元数据[base，base+size].
// 它可能会分配元数据，在这种情况下，*p.sysStat将被更新。
// 
// p.mheapLock必须保持。
func (p *pageAlloc) grow(base, size uintptr) {
	assertLockHeld(p.mheapLock)

	// 四舍五入到chunk，因为我们无法处理比chunk更小的增量
	// 而且，sysGrow需要对齐的值。
	limit := alignUp(base+size, pallocChunkBytes)
	base = alignDown(base, pallocChunkBytes)

	// 以依赖于系统的方式增加摘要级别。
	// 我们只是在这里更新了一堆额外的元数据。
	p.sysGrow(base, limit)

	// 更新p.start和p.end.
	// 如果还没有增加，则start==0。这通常是
	// 由于零页未映射，因此安全。
	firstGrowth := p.start == 0
	start, end := chunkIndex(base), chunkIndex(limit)
	if firstGrowth || start < p.start {
		p.start = start
	}
	if end > p.end {
		p.end = end
	}
	// 注意[base，limit]永远不会与任何现有的
	// 范围重叠，因为grow只会将从未使用过的内存
	// 区域添加到页面分配器中。
	p.inUse.add(makeAddrRange(base, limit))

	// grow操作非常类似于自由操作，因此如果我们的
	// 块最终低于p.searchAddr，请将p.searchAddr更新为
	// 新地址，就像在free中一样。
	if b := (offAddr{base}); b.lessThan(p.searchAddr) {
		p.searchAddr = b
	}

	// 将条目添加到块中，如果需要，这些块是稀疏的。然后，
	// 初始化位图。
	// 
	// 新增长的内存始终被视为已清除。
	// 将已清除位图中的所有位设置为高位。
	for c := chunkIndex(base); c < chunkIndex(limit); c++ {
		if p.chunks[c.l1()] == nil {
			// 创建必要的二级条目。
			// 
			// 以原子方式存储它，以避免与读卡器竞争，而这些读卡器
			// 没有获得堆锁。
			r := sysAlloc(unsafe.Sizeof(*p.chunks[0]), p.sysStat)
			if r == nil {
				throw("pageAlloc: out of memory")
			}
			atomic.StorepNoWB(unsafe.Pointer(&p.chunks[c.l1()]), r)
		}
		p.chunkOf(c).scavenged.setRange(0, pallocChunkPages)
	}

	// 相应地更新摘要。增长就像一个空闲的，所以
	// 我们需要确保这个新空闲的内存是可访问的
	// 摘要中的ble.
	p.update(base, size/pageSize, true, false)
}

// 更新堆元数据。每次更新位图
// 时都必须调用它。
// 
// 如果contig为true，则更新会进行一些优化，假设在addr和ddr+npages.alloc表示
// 执行的操作是分配还是自由操作。
// 
// 必须保留p.mheapLock。
func (p *pageAlloc) update(base, npages uintptr, contig, alloc bool) {
	assertLockHeld(p.mheapLock)

	// 包含基、限制、开始和结束。
	limit := base + npages*pageSize - 1
	sc, ec := chunkIndex(base), chunkIndex(limit)

	// 首先处理更新最低级别。
	if sc == ec {
		// 快速路径：分配不跨越多个区块，
		// 因此更新此区块，如果摘要没有更改，则返回。
		x := p.summary[len(p.summary)-1][sc]
		y := p.chunkOf(sc).summarize()
		if x == y {
			return
		}
		p.summary[len(p.summary)-1][sc] = y
	} else if contig {
		// 慢速连续路径：分配跨越多个区块
		// 并且保证至少有一个摘要会更改。
		summary := p.summary[len(p.summary)-1]

		// 更新区块sc的摘要。
		summary[sc] = p.chunkOf(sc).summarize()

		// 更新中间块的摘要，即
		// 完全分配或释放。
		whole := p.summary[len(p.summary)-1][sc+1 : ec]
		if alloc {
			// 应优化为memclr。
			for i := range whole {
				whole[i] = 0
			}
		} else {
			for i := range whole {
				whole[i] = freeChunkSum
			}
		}

		// 更新块ec的摘要。
		summary[ec] = p.chunkOf(ec).summarize()
	} else {
		// 慢速常规路径：分配跨越多个块
		// 和至少一个摘要y肯定会更改。
		// 
		// 我们不能假设发生了连续分配，所以请遍历
		// 范围内的每个块并手动重新计算摘要。
		summary := p.summary[len(p.summary)-1]
		for c := sc; c <= ec; c++ {
			summary[c] = p.chunkOf(c).summarize()
		}
	}

	// 遍历基数树并适当更新摘要。
	changed := true
	for l := len(p.summary) - 2; l >= 0 && changed; l-- {
		// 在级别更新摘要l来自l+1级总结。
		changed = false

		// /“常数”对于上一个级别，我们需要从该级别计算摘要。
		logEntriesPerBlock := levelBits[l+1]
		logMaxPages := levelLogPages[l+1]

		// lo和hi描述我们需要查看的级别的所有部分。
		lo, hi := addrsToSummaryRange(l, base, limit+1)

		// 迭代每个块，在不太精细的级别更新相应的摘要。
		for i := lo; i < hi; i++ {
			children := p.summary[l+1][i<<logEntriesPerBlock : (i+1)<<logEntriesPerBlock]
			sum := mergeSummaries(children, logMaxPages)
			old := p.summary[l][i]
			if old != sum {
				changed = true
				p.summary[l][i] = sum
			}
		}
	}
}

// allocRange标记m的范围埃默里[base，base+npages*pageSize]作为
// 分配。它还更新摘要以反映最新更新的
// 位图。
// 
// 返回
// 分配范围内的已清除内存量（字节）。
// 
// p.mheapLock必须为HOLD.
func (p *pageAlloc) allocRange(base, npages uintptr) uintptr {
	assertLockHeld(p.mheapLock)

	limit := base + npages*pageSize - 1
	sc, ec := chunkIndex(base), chunkIndex(limit)
	si, ei := chunkPageIndex(base), chunkPageIndex(limit)

	scav := uint(0)
	if sc == ec {
		// 该范围不跨越任何区块边界。
		chunk := p.chunkOf(sc)
		scav += chunk.scavenged.popcntRange(si, ei+1-si)
		chunk.allocRange(si, ei+1-si)
	} else {
		// 该范围至少跨越一个区块边界。
		chunk := p.chunkOf(sc)
		scav += chunk.scavenged.popcntRange(si, pallocChunkPages-si)
		chunk.allocRange(si, pallocChunkPages-si)
		for c := sc + 1; c < ec; c++ {
			chunk := p.chunkOf(c)
			scav += chunk.scavenged.popcntRange(0, pallocChunkPages)
			chunk.allocAll()
		}
		chunk = p.chunkOf(ec)
		scav += chunk.scavenged.popcntRange(0, ei+1)
		chunk.allocRange(0, ei+1)
	}
	p.update(base, npages, true, true)
	return uintptr(scav) * pageSize
}

// FindMappedDR返回最小的映射offAddr，即
// />=addr。也就是说，如果addr引用映射内存，则返回的是
// 如果addr较高她比任何映射的区域都要大，那么它返回maxOffAddr.
// 
// p.mheapLock必须保持。如果我们不在测试中，首先通过检查mheap_.arenas.
func (p *pageAlloc) findMappedAddr(addr offAddr) offAddr {
	assertLockHeld(p.mheapLock)

	// 这是一条快速路径，只能在测试之外安全使用。
	ai := arenaIndex(addr.addr())
	if p.test || mheap_.arenas[ai.l1()] == nil || mheap_.arenas[ai.l1()][ai.l2()] == nil {
		vAddr, ok := p.inUse.findAddrGreaterEqual(addr.addr())
		if ok {
			return offAddr{vAddr}
		} else {
			// candi日期搜索地址大于任何
			// 已知地址，这意味着我们肯定没有剩余的
			// 可用内存。
			return maxOffAddr
		}
	}
	return addr
}

// 查找搜索第一个地址（按顺序排列的地址）
// n连续的自由区域大小显示并返回该区域的基址。
// 
// 它使用p.searchAddr删减其搜索，并假设chunkIndex（p.searchAddr）下没有palloc块
// 包含所有可用内存。
// 
// find还计算并返回一个候选p.searchAddr，该候选p.searchAddr或
// 可能不会比p.searchAddr已经删除的地址空间多。
// 此候选人始终是有效的p.searchAddr。
// 
// find表示慢路径和完整的基树搜索。
// 
// 失败时返回0的基址，在这种情况下，返回的候选
// searchAddr无效，必须忽略。
// 
// p.mheapLock必须保持。
func (p *pageAlloc) find(npages uintptr) (uintptr, offAddr) {
	assertLockHeld(p.mheapLock)

	// 搜索算法。
	// 
	// 此算法将基数树的每个级别l从根级别
	// 移动到叶级别。它在基树的给定级别中最多迭代1个<<levelBits[l]项
	// 并使用摘要信息
	// 查找：
	// 1）给定子树包含足够大的连续区域，在
	// 它将在下一个级别上继续迭代，或者
	// 2）有足够的连续边界交叉位来满足
	// 分配，在这一点它确切地知道从何处开始
	// 分配。
	// 
	// 我将索引跟踪到我们实际感兴趣的
	// 连续1<<levelBits[l]项的当前级别l的结构中。
	// 
	// 注意：从技术上讲，此搜索可以分配一个跨越
	// ARENABASESOFFSET边界的区域，当ARENABASESOFFSET！=0，是
	// 不连续。但是，唯一可能发生这种情况的方法是映射零地址处的
	// 页面，而这在
	// 上是不可能的，因为我们支持的每个系统都有arenaBaseOffset！=0因此，操作系统将永远不会为我们映射零页，而这个函数不会试图以任何方式处理这种情况，因此，不连续性已经被编码。

	// i是我们在当前级别搜索的条目块的开头。
	i := 0

	// firstFree是地址空间的区域，我们肯定会找到堆中的第一个空闲页。base和bound是此窗口的包含
	// 边界，两者都是地址空间的线性化、连续
	// 视图中的地址（预先添加了arenaBaseOffset）。在每个级别上，当我们找到包含第一个可用内存页的内存区域时，这个窗口会缩小。首先，该范围反映了
	// 整个进程地址空间。
	// 
	// 每次发现
	// 堆中的可用空间时，通过调用foundFree更新firstFree。
	// 
	// 在搜索结束时，base.addr（）是我们在此搜索中可以推断出的最好的新
	// searchAddr。
	firstFree := struct {
		base, bound offAddr
	}{
		base:  minOffAddr,
		bound: maxOffAddr,
	}
	// foundFree接受给定的地址范围[addr，addr+size）和
	// 如果范围较窄，则更新firstFree。输入范围必须
	// 要么完全包含在firstFree中，要么不与之重叠
	// 完全。
	// 
	// 这样，我们将记录我们在任何自由
	// 该摘要，则缩小范围。但一旦我们需要在该摘要之外进行迭代，以找到足够大的范围，我们将停止缩小范围。
	foundFree := func(addr offAddr, size uintptr) {
		if firstFree.base.lessEqual(addr) && addr.add(size-1).lessEqual(firstFree.bound) {
			// 该范围适合当前的第一个自由窗口，因此缩小
			// 将firstFree窗口向下移动到此范围的底部和边界。
			firstFree.base = addr
			firstFree.bound = addr.add(size - 1)
		} else if !(addr.add(size-1).lessThan(firstFree.base) || firstFree.bound.lessThan(addr)) {
			// 此范围仅与firstFree范围部分重叠，
			// 因此抛出。
			print("runtime: addr = ", hex(addr.addr()), ", size = ", size, "\n")
			print("runtime: base = ", hex(firstFree.base.addr()), ", bound = ", hex(firstFree.bound.addr()), "\n")
			throw("range partially overlaps")
		}
	}

	// lastSum是我们在上一级别上看到的摘要，它使我们
	// 进入下一级别。用于打印其他内容
	// 灾难性故障案例中的信息。
	// lastSumIdx是上一级别的摘要索引。
	lastSum := packPallocSum(0, 0, 0)
	lastSumIdx := -1

nextLevel:
	for l := 0; l < len(p.summary); l++ {
		// 对于根级别，entriesPerBlock是整个级别。
		entriesPerBlock := 1 << levelBits[l]
		logMaxPages := levelLogPages[l]

		// 我们已经进入了一个新级别，所以让我们将i更新为新的
		// 开始索引。这对于级别0是不可行的。
		i <<= levelBits[l]

		// 切掉我们关心的条目块。
		entries := p.summary[l][i : i+entriesPerBlock]

		// 确定j0，这是我们应该开始迭代的第一个索引。
		// 如果我们在上一级别遵循
		// searchAddr，或者我们在根l上，searchAddr可以帮助我们消除迭代eve，其中
		// 在levelShift.
		j0 := 0
		if searchIdx := offAddrToLevelIndex(l, p.searchAddr); searchIdx&^(entriesPerBlock-1) == i {
			j0 = searchIdx & (entriesPerBlock - 1)
		}

		// 在级别项上运行以查找
		// 在一个项内或在多个项之间连续运行至少N个页面。
		// 
		// base包含当前
		// 第一个条目的第一个页面）。
		// 连续页面运行的页面索引（相对于
		// 
		// size包含当前考虑的连续页面运行的大小。
		var base, size uint
		for j := j0; j < len(entries); j++ {
			sum := entries[j]
			if sum == 0 {
				// 完整输入意味着我们打破了任何连续记录，
				// 我们应该完全跳过它。
				size = 0
				continue
			}

			// 我们遇到了一个非零的摘要，这意味着
			// 释放内存，所以更新firstFree。
			foundFree(levelIndexToOffAddr(l, i+j), (uintptr(1)<<logMaxPages)*pageSize)

			s := sum.start()
			if size+s >= uint(npages) {
				// 如果size==0，我们还没有运行，这意味着base无效。因此，将
				// base设置为该块的第一页。
				if size == 0 {
					base = uint(j) << logMaxPages
				}
				// 我们击中了npages；我们完了！
				size += s
				break
			}
			if sum.max() >= uint(npages) {
				// 条目本身包含npages连续的
				// 空闲页面，因此继续下一级
				// 以查找该运行。
				i += j
				lastSumIdx = i
				lastSum = sum
				continue nextLevel
			}
			if size == 0 || s < 1<<logMaxPages {
				// 我们可能没有启动当前运行，或者此项
				// 不是完全免费的（这意味着我们无法继续当前的
				// 运行），因此请尝试根据sum.end设置大小和基础
				// 来开始新的运行。
				size = sum.end()
				base = uint(j+1)<<logMaxPages - size
				continue
			}
			// 该条目完全免费，因此继续运行。
			size += 1 << logMaxPages
		}
		if size >= uint(npages) {
			// 我们发现有足够多的免费页面跨越了
			// 一些边界，因此计算地址并返回它。
			addr := levelIndexToOffAddr(l, i).add(uintptr(base) * pageSize).addr()
			return addr, p.findMappedAddr(firstFree.base)
		}
		if l == 0 {
			// 我们处于零级，这意味着我们已经搜索完了。
			return 0, maxSearchAddr
		}

		// 我们没有处于零级，我们已经耗尽了我们所寻找的级别。
		// 这意味着要么我们的计算错误，要么高于
		// 的水平欺骗了我们。在这两种情况下，转储一些有用的状态并抛出。
		print("runtime: summary[", l-1, "][", lastSumIdx, "] = ", lastSum.start(), ", ", lastSum.max(), ", ", lastSum.end(), "\n")
		print("runtime: level = ", l, ", npages = ", npages, ", j0 = ", j0, "\n")
		print("runtime: p.searchAddr = ", hex(p.searchAddr.addr()), ", i = ", i, "\n")
		print("runtime: levelShift[level] = ", levelShift[l], ", levelBits[level] = ", levelBits[l], "\n")
		for j := 0; j < len(entries); j++ {
			sum := entries[j]
			print("runtime: summary[", l, "][", i+j, "] = (", sum.start(), ", ", sum.max(), ", ", sum.end(), ")\n")
		}
		throw("bad summary data")
	}

	// 既然我们已经到了这一点，那就意味着我们还没有找到一个足够大小的自由区域跨越某些边界（块或更大）。
	// 这意味着我们检查的最后一个摘要必须有一个足够大的“max”
	// 值，因此请查看区块内部以找到合适的运行。
	// 
	// 在迭代所有级别后，我必须包含一个块索引，该块索引
	// 是最终级别所表示的。
	ci := chunkIdx(i)
	j, searchIdx := p.chunkOf(ci).find(npages, 0)
	if j == ^uint(0) {
		// 尽管摘要告诉我们它应该在那里，但我们在这个区块中找不到任何空间。可能有bug，所以转储一些状态并抛出。
		sum := p.summary[len(p.summary)-1][i]
		print("runtime: summary[", len(p.summary)-1, "][", i, "] = (", sum.start(), ", ", sum.max(), ", ", sum.end(), ")\n")
		print("runtime: npages = ", npages, "\n")
		throw("bad summary data")
	}

	// 计算空闲空间开始的地址。
	addr := chunkBase(ci) + uintptr(j)*pageSize

	// 由于我们实际搜索了块，我们可能已经找到了一个更窄的自由窗口。
	searchAddr := chunkBase(ci) + uintptr(searchIdx)*pageSize
	foundFree(offAddr{searchAddr}, chunkBase(ci+1)-searchAddr)
	return addr, p.findMappedAddr(firstFree.base)
}

// alloc从页堆中分配相当于npages的内存，返回分配的基本
// 地址和区域中包含的清除内存量（字节）[base address，base address+npages*pageSize）.
// 
// 在失败时返回0基地址，在这种情况下，其他返回值
// 应被忽略。
// 
// p.mheapLock必须被保留。
// 
// 必须在系统堆栈上运行，因为p.mheapLock必须被保留。
// 
// go:systemstack 
func (p *pageAlloc) alloc(npages uintptr) (addr uintptr, scav uintptr) {
	assertLockHeld(p.mheapLock)

	// 如果searchAddr所指的区域的地址高于
	// 任何已知的块，那么我们就知道内存不足。
	if chunkIndex(p.searchAddr.addr()) >= p.end {
		return 0, 0
	}

	// 如果npages有机会适合searchAddr所在的块，
	// 直接搜索。
	searchAddr := minOffAddr
	if pallocChunkPages-chunkPageIndex(p.searchAddr.addr()) >= uint(npages) {
		// 此处的npages保证不大于pallocChunkPages。
		i := chunkIndex(p.searchAddr.addr())
		if max := p.summary[len(p.summary)-1][i].max(); max >= uint(npages) {
			j, searchIdx := p.chunkOf(i).find(npages, chunkPageIndex(p.searchAddr.addr()))
			if j == ^uint(0) {
				print("runtime: max = ", max, ", npages = ", npages, "\n")
				print("runtime: searchIdx = ", chunkPageIndex(p.searchAddr.addr()), ", p.searchAddr = ", hex(p.searchAddr.addr()), "\n")
				throw("bad summary data")
			}
			addr = chunkBase(i) + uintptr(j)*pageSize
			searchAddr = offAddr{chunkBase(i) + uintptr(searchIdx)*pageSize}
			goto Found
		}
	}
	// 由于各种原因，我们无法使用searchAddr，因此请尝试使用
	// 缓慢的路径。
	addr, searchAddr = p.find(npages)
	if addr == 0 {
		if npages == 1 {
			// 我们无法找到一个空闲页面，即分配的最小单元
			// 我们无法找到一个空闲页面。这意味着我们知道堆已完全耗尽。否则，堆中可能仍然有可用的空间，只是没有足够的连续空间来容纳npages。现在我们有了地址，请继续实际标记位。如果在更高的searchAddr中，我们知道偏移地址空间中searchAddr之前的所有堆内存都已分配，因此将p.searchAddr升级到新的一个必须保持锁定。必须在系统堆栈上运行
			p.searchAddr = maxSearchAddr
		}
		return 0, 0
	}
Found:
	scav = p.allocRange(addr, npages)

	if p.searchAddr.lessThan(searchAddr) {
		p.searchAddr = searchAddr
	}
	return addr, scav
}

// 
// 因为必须保持p.mheapLock。
// 
// go:systemstack 
func (p *pageAlloc) free(base, npages uintptr) {
	assertLockHeld(p.mheapLock)

	// 如果我们正在释放p.searchAddr下面的页面，请更新searchAddr。
	if b := (offAddr{base}); b.lessThan(p.searchAddr) {
		p.searchAddr = b
	}
	// 更新清道夫的免费高水位线。
	limit := base + npages*pageSize - 1
	if offLimit := (offAddr{limit}); p.scav.freeHWM.lessThan(offLimit) {
		p.scav.freeHWM = offLimit
	}
	if npages == 1 {
		// 快速路径：我们正在清除一个位，我们确切地知道它在哪里，所以直接标记它。
		i := chunkIndex(base)
		p.chunkOf(i).free1(chunkPageIndex(base))
	} else {
		// 慢路径：我们正在清除更多位，因此可能需要迭代。
		sc, ec := chunkIndex(base), chunkIndex(limit)
		si, ei := chunkPageIndex(base), chunkPageIndex(limit)

		if sc == ec {
			// 该范围不跨越任何区块边界。
			p.chunkOf(sc).free(si, ei+1-si)
		} else {
			// 范围至少跨越一个区块边界。
			p.chunkOf(sc).free(si, pallocChunkPages-si)
			for c := sc + 1; c < ec; c++ {
				p.chunkOf(c).freeAll()
			}
			p.chunkOf(ec).free(0, ei+1)
		}
	}
	p.update(base, npages, true, false)
}

const (
	pallocSumBytes = unsafe.Sizeof(pallocSum(0))

	// maxPackedValue是
	// pallocSum中三个字段中的任何一个可以使用的最大值。
	maxPackedValue    = 1 << logMaxPackedValue
	logMaxPackedValue = logPallocChunkPages + (summaryLevels-1)*summaryLevelBits

	freeChunkSum = pallocSum(uint64(pallocChunkPages) |
		uint64(pallocChunkPages<<logMaxPackedValue) |
		uint64(pallocChunkPages<<(2*logMaxPackedValue)))
)

// pallocSum是一种压缩的摘要类型，它将三个数字打包为一个8字节的值：start、max、
// 和end。这些值中的每一个都是位图
// 的摘要，因此是计数，每个值的最大值可能是
// 2^21-1，或者所有三个值都可能等于2^21。后一种情况表示为
// 只需设置第64位。
type pallocSum uint64

// packPallocSum获取起始值、最大值和结束值，并生成一个pallocSum。
func packPallocSum(start, max, end uint) pallocSum {
	if max == maxPackedValue {
		return pallocSum(uint64(1 << 63))
	}
	return pallocSum((uint64(start) & (maxPackedValue - 1)) |
		((uint64(max) & (maxPackedValue - 1)) << logMaxPackedValue) |
		((uint64(end) & (maxPackedValue - 1)) << (2 * logMaxPackedValue)))
}

// start从压缩和中提取起始值。
func (p pallocSum) start() uint {
	if uint64(p)&uint64(1<<63) != 0 {
		return maxPackedValue
	}
	return uint(uint64(p) & (maxPackedValue - 1))
}

// max从压缩和中提取最大值。
func (p pallocSum) max() uint {
	if uint64(p)&uint64(1<<63) != 0 {
		return maxPackedValue
	}
	return uint((uint64(p) >> logMaxPackedValue) & (maxPackedValue - 1))
}

// end从压缩和中提取结束值。
func (p pallocSum) end() uint {
	if uint64(p)&uint64(1<<63) != 0 {
		return maxPackedValue
	}
	return uint((uint64(p) >> (2 * logMaxPackedValue)) & (maxPackedValue - 1))
}

// unpack解压摘要中的所有三个值。
func (p pallocSum) unpack() (uint, uint, uint) {
	if uint64(p)&uint64(1<<63) != 0 {
		return maxPackedValue, maxPackedValue, maxPackedValue
	}
	return uint(uint64(p) & (maxPackedValue - 1)),
		uint((uint64(p) >> logMaxPackedValue) & (maxPackedValue - 1)),
		uint((uint64(p) >> (2 * logMaxPackedValue)) & (maxPackedValue - 1))
}

// 合并摘要将每个可能在
// 中表示的连续摘要合并为一个。
func mergeSummaries(sums []pallocSum, logMaxPagesPerSum uint) pallocSum {
	// 将汇总合并为一个汇总。
	// 
	// 我们通过保存一个表示合并
	// 开始、最大和结束时的总和[：i]的运行摘要来实现这一点。
	start, max, end := sums[0].unpack()
	for i := 1; i < len(sums); i++ {
		// 合并为和[i]。
		si, mi, ei := sums[i].unpack()

		// 合并在总和[i]中。仅当运行摘要是
		// 完全自由时启动，否则此摘要的start 
		// 在合并总和中不起作用。
		if start == uint(i)<<logMaxPagesPerSum {
			start += si
		}

		// 通过查看
		// 运行和和[i]
		// 之间的边界，并在最大和[i]处重新计算运行和的最大值，取这两个
		// 中的最大值和运行和的最大值。
		if end+si > max {
			max = end + si
		}
		if mi > max {
			max = mi
		}

		// 通过检查此新摘要是否完全免费，最终合并。如果是，那么我们希望扩展运行总和的
		// 以新的摘要结束。如果没有，那么我们有一些分配的
		// 页面，我们只想取
		// sums[i]中的最终值。
		if ei == 1<<logMaxPagesPerSum {
			end += 1 << logMaxPagesPerSum
		} else {
			end = ei
		}
	}
	return packPallocSum(start, max, end)
}
